/* 	
		This is ol' doubly-linked list implementation
		It works funny but it does.
		If you use it please don't remove my humble name n address
		Alexey Serikov <alex@spaininn.com>
*/

#include "amever.h"

struct chain_node *chain_nodeInit
(struct chain_set *parent, void *val, unsigned int pos, struct chain_node *me) {
	if (!parent) return 0;
	if (parent->maxlen <= parent->len) {
		amelog("Cannot add %dnth node to %ded chain.\n", parent->len, parent->maxlen);
		return 0;
	}
	if (!me) {
		me = chain_getNode();
		me->parent = parent;
		me->index = pos;
		me->val = val;
	}

	if (pos == 0 || parent->first == 0 || pos < parent->first->index) {
		if (parent->first) {
			CHAIN_PUSHB(parent->first, me);
		}
		else {
			parent->first = me;
			parent->last = me;
			me->next = 0;
			me->prev = 0;
			me->parent = parent;
			me->parent->len++;
		}
	}
	else if (pos >= parent->last->index) {
		CHAIN_PUSHA(parent->last, me);
	}
	else {
		register struct chain_node *noderator;
		register short unsigned i;
		unsigned int bestres =
			(parent->last->index - pos) > (pos - parent->first->index) ?
			(pos - parent->first->index) : (parent->last->index - pos);
		noderator =
         (parent->last->index - pos) > (pos - parent->first->index) ?
			 parent->first : parent->last;
		if (parent->len > MILE) {
			for (i=0;i<CHAIN_MILESTONES;i++) {
				if (noderator && parent->milestones[i] && (unsigned)parent->milestones[i]->index - pos < bestres) {
					bestres = (unsigned)parent->milestones[i]->index - pos;
					noderator = parent->milestones[i];
				}
			}
		}
		register int _MILE = (int)(parent->len / CHAIN_MILESTONES);
		if (noderator->index < pos) {
			for (i=0;noderator->index < pos;noderator = noderator->next,i++) {
				if  (noderator && i && _MILE && !(i % _MILE )) {
					parent->milestones[(unsigned int)(i % CHAIN_MILESTONES)] = noderator;
				}
			}
			if (noderator) {
				CHAIN_PUSHB(noderator, me);
			}
		}
		else {
			for(i=0; noderator->index > pos;noderator = noderator->prev,i++) {
				if (noderator && i && _MILE && !(i % _MILE ))  {
					parent->milestones[(unsigned int)(i % CHAIN_MILESTONES)] = noderator;
				}
			}
			if (noderator) {
				CHAIN_PUSHA(noderator, me);
			}
		}
		if (!me->parent) {
			chain_nodeShut(me);
			me = 0;
		}
	}
	if (!me) {
		amelog("node init failed.\n");
		return NULL;
	}
	return me;
}

int chain_nodeShut(struct chain_node *me) {
	if (me == NULL || !me) return;
	if (me->parent) {
		short int i;
		if (me->parent->len > MILE)
			for (i=1; i<CHAIN_MILESTONES && me->parent->milestones[i] > 0 ;i++)
				if (me->parent->milestones[i] == me)
					me->parent->milestones[i] = 0;
		CHAIN_UNLINK(me);
	}
	memset(me, 0, sizeof(struct chain_node));
	if (s.freeNodes->len > s.freeNodes->maxlen) {
		free(me);
	}
	else {
		if (s.freeNodes->last) {
			me->prev = s.freeNodes->last;
			s.freeNodes->last->next = me;
			s.freeNodes->last = me;
			s.freeNodes->len++;
		}
		else {
			s.freeNodes->last =s.freeNodes->first = me;
			s.freeNodes->len = 1;
		}
	}
	return 1;
}

int chain_nodeShutI(struct chain_node *me) {
	memset(me, 0, sizeof(struct chain_node));
	if (s.freeNodes->len > s.freeNodes->maxlen) {
		free(me);
	}
	else if ((s.freeNodes->first) && (s.freeNodes->last)) {
		me->prev = s.freeNodes->last;
		s.freeNodes->last->next = me;
		s.freeNodes->last = me;
		s.freeNodes->len++;
	}
	else {
		s.freeNodes->last =s.freeNodes->first = me;
		s.freeNodes->len = 1;
	}
}

struct chain_set * chain_setInit(void *p, int type, int maxlen) {
	struct chain_set *me = malloc(sizeof(struct chain_set) + 255); // freed int chain_setShut
	me->last = NULL;
	me->first = NULL;
	me->len = 0;
	me->contiguous = 1;
	me->val = (void *)p;

	if (maxlen == 0) {
		me->maxlen = 0xFF;
	}
	else {
		me->maxlen = maxlen;
	}
	return me;
}

void chain_setShut(struct chain_set *me)  {
	chain_setClear(me);
	free(me);
	me = 0;
}

void chain_setClear(struct chain_set *me) {
	amelog("Clearing 0x%x.\n", me);
#ifdef CHAIN_SETCLEAR_FAST
	if (s.freeNodes->len < s.freeNodes->maxlen) {
		if (s.freeNodes->first && s.freeNodes->last && s.freeNodes->len) {
			s.freeNodes->last->next = me->first;
			s.freeNodes->last = me->last;
			s.freeNodes->len += me->len;
		}
		else {
			s.freeNodes->first = me->first;
			s.freeNodes->last = me->last;
			s.freeNodes->len = me->len;
		}
		me->first = me->last = NULL;
		me->len = 0;
	}
	else {
#endif
		struct chain_node *noderator = me->first;
		struct chain_node *tmp;
		while (noderator) {
			tmp = noderator;
			noderator = noderator->next;
			chain_nodeShut(tmp);
		}
		chain_nodeShut(noderator);
		me->len = 0; me->first = me->last = 0;
#ifdef CHAIN_SETCLEAR_FAST
	}
#endif
}

struct chain_node *chain_insertUnique(struct chain_set *set, int pos, void *val, unsigned char replace) {
	struct chain_node *node = chain_findIndex(set, pos);
	if (!node) {
		node = chain_getNode();
		node->index = pos;
		node->val = val;
		node->parent = set;
		node->parent->first = node->parent->last = node;
		node->next = node->prev = 0;
		set->len++;
		return node;
	}
	else if (node->index == pos) {
		if (replace) {
			node->val = val;
			return node;
		}
		return 0;
	}

	struct chain_node *result = chain_getNode();
	result->val = val;
	result->index = pos;

	if (node->index > pos) {
		CHAIN_PUSHB(node, result);
	}
	else {
		CHAIN_PUSHA(node, result);
	}
	result->parent = set;
	return result;
}



struct chain_node *chain_getNode(void) {
	struct chain_node *result;
	if (s.freeNodes->first) {
		result = s.freeNodes->first;
		if (result == s.freeNodes->last)
			s.freeNodes->last = s.freeNodes->first = 0,s.freeNodes->len = 0;
		else
			s.freeNodes->first = result->next;
	}
	else {
		result = (struct chain_node *)malloc(sizeof(struct chain_node));
	}
	memset(result, 0, sizeof(struct chain_node));
	return result;
}

struct chain_node *chain_findExactIndex(struct chain_set *parent, int pos) {
	struct chain_node *node = chain_findIndex(parent, pos);
	if (node && node->index == pos)
		return node;
	else
		return 0;
}


struct chain_node *chain_findIndex (struct chain_set *parent, int pos) {
	/* Very relatively quick find, returns the first nearest element, supposingly */
	if (parent == NULL || parent->first == NULL)
		return 0;
	if (pos < parent->first->index)
		return parent->first;
	if (pos > parent->last->index)
		return parent->last;

	if (parent->first == NULL || pos <= parent->first->index) {
		return parent->first;
	}
	else if (pos >= parent->last->index) {
		return parent->last;
	}
	else if (parent->len < MILE) {
		struct chain_node *noderator =
				(parent->last->index - pos) > (pos - parent->first->index) ?
				parent->first : parent->last;
		if (parent->last->index - pos > pos - parent->first->index) {
			for (noderator = parent->first;noderator->index < pos;noderator = noderator->next);
		}
		else {
			for(noderator = parent->last;noderator->index > pos;noderator = noderator->prev);
		}
		return noderator;
	}
	else {
		struct chain_node *noderator;
		int i;
		unsigned int bestres =
				(parent->last->index - pos) > (pos - parent->first->index) ?
				(pos - parent->first->index) : (parent->last->index - pos);
		noderator =
				(parent->last->index - pos) > (pos - parent->first->index) ?
				parent->first : parent->last;

		for (i=1;i<CHAIN_MILESTONES && parent->milestones[i] > 0;i++) {
			if (parent->milestones[i] && (unsigned)parent->milestones[i]->index - pos < bestres) {
				bestres = (unsigned)parent->milestones[i]->index - pos;
				noderator = parent->milestones[i];
			}
		}

		int _MILE = (int)(parent->len / CHAIN_MILESTONES);

		if (noderator->index < pos) {
			for (i=0;noderator->index < pos;noderator = noderator->next,i++) {
				if  (noderator && i && _MILE && !(i % _MILE )) {
					parent->milestones[(unsigned int)(i % CHAIN_MILESTONES)] = noderator;
				}
			}
		}
		else {
			for(i=0; noderator->index > pos;noderator = noderator->prev,i++) {
				if (noderator && i && _MILE && !(i % _MILE ))  {
					parent->milestones[(unsigned int)(i % CHAIN_MILESTONES)] = noderator;
				}
			}
		}
		return noderator;
	}
	return 0;
}

struct chain_set *chain_setInvert (struct chain_set *old) {
	struct chain_set *newset = chain_setInit(0,0,255);
	struct chain_node *node;
	for (node=old->last;node;node=node->prev)
		chain_nodeInit(newset,node->val,1,0);
	return newset;
}
